#include <iostream>
#include <string>
#include "list.h"
#include "typeinfo.h"

using namespace std;

/*
 * 将链表2，合并到链表1中
 *
 * @param  &listOne  SingleList 链表类型
 * @param  &listTwo  SingleList 链表类型 
 */
void mergeNotDecend(SingleList &listOne, SingleList &listTwo)
{
    LNode * headOne, *headTwo, *headMerge, *curMerge;

    headOne = listOne.getHead(); 
    headTwo = listTwo.getHead(); 

    //先比较第一个节点大小
  
    if(headOne ==NULL && headTwo ==NULL){
        //如果都为空，直接返回
        return ;
    }else if(headOne == NULL && headTwo != NULL){
        //如果链表一当前指针为空，则直接处理链表二
        curMerge = headMerge = headTwo;
    }else if(headOne != NULL && headTwo == NULL){
        //如果链表二当前指针为空，则直接处理链表一
        curMerge = headMerge = headOne;
    }else{
        if(headOne->data >= headTwo->data){
            //如果链表一的值不比链表二的值小，则处理链表一
            curMerge = headMerge = headTwo;
            if(headTwo->link != NULL){
                //链表一的指针往后移动
                headTwo = headTwo->link;
            } 
        }else{
            //如果链表二的值不比链表一的值小，则处理链表一
            curMerge = headMerge = headOne;
            if(headOne->link != NULL){
                headOne = headOne->link;
            }
        }
    }


    //循环比较
    while(headOne != NULL || headTwo != NULL){
        //如果两个链表都不为空
        if(headOne != NULL &&  headTwo != NULL ){
            if(headOne->data <= headTwo->data){
                if(curMerge->data < headOne->data){ //只有大于当前合并的数才移动Merge
                    curMerge->link = headOne;
                    curMerge = headOne; //移动指针到下一个节点
                }

                if(headOne->link != NULL){
                    headOne = headOne->link;
                }else{
                  headOne = NULL;
                }
            }else{
                if(curMerge->data < headTwo->data){ //只有大于当前合并的数才移动Merge
                    curMerge->link = headTwo;
                    curMerge = headTwo; //移动指针到下一个节点
                }

                if(headTwo->link != NULL){
                    headTwo = headTwo->link;
                }else{
                   headTwo = NULL;
                }
            }
        }else if(headOne == NULL && headTwo != NULL){
            if(curMerge->data < headTwo->data){ //只有大于当前合并的数才移动Merge
                curMerge->link = headTwo;
                curMerge = headTwo; //移动指针到下一个节点
            }
            if(headTwo->link != NULL){
                headTwo = headTwo->link;
            }else{
                headTwo = NULL;
            }
        }else if(headOne != NULL && headTwo == NULL){
            if(curMerge->data < headOne->data){ //只有大于当前合并的数才移动Merge
                curMerge->link = headOne;
                curMerge = headOne; //移动指针到下一个节点
            }

            if(headOne->link != NULL){
                headOne = headOne->link;
            }else{
               headOne = NULL;
            }

        }

    }
    //设置链表一的头指针指向新链表的第一个节点
    listOne.setHead(headMerge);

    return; 
}

int main(){
    cout  << "请输入若干个非递减数字，每输入一个按Enter键，最后输入任意字母表示结束:\n";
    SingleList ListOne, ListTwo;  

    int m,n;
    //输入第一个链表
    while(cin >>n){
        if(typeid(n) != typeid(int)){
            break;
        }
        if(ListOne.getLast() !=NULL && ListOne.getLast()->data >  n){
            cout << "请输入非递减数\n";
            continue;
        }
        LNode *node = new LNode(n);
        ListOne.insert(node, ListOne.getLen());
    }
    //输出输入结果
    cout << "链表一:";
    ListOne.output();
    cout <<"链表长度：" <<ListOne.getLen()<<"\n";
 
    //输入第二个链表
    cout  << "第二个链表：请输入若干个非递减数字，每输入一个按Enter键，最后输入任意字母表示结束:\n";
    //清空io缓存
    cin.clear();
    getchar();
    while(cin>>m){
        if(typeid(m) != typeid(int)){
            break;
        }
        if(ListTwo.getLast() !=NULL && ListTwo.getLast()->data >m){
            cout << "请输入非递减数\n";
            continue;
        }
        LNode *node = new LNode(m);
        ListTwo.insert(node, ListTwo.getLen());
    }
    //输出输入结果
    cout << "链表二:";
    ListTwo.output();
    cout <<"链表长度：" <<ListTwo.getLen()<<"\n";


    //合并链表2到1--去重非递减
    mergeNotDecend(ListOne, ListTwo);

    //输出合并后的列表
    cout << "链表合并:";
    ListOne.output();
    cout <<"链表长度：" <<ListOne.getLen()<<"\n";


   return 0;  
}
